//import java.util.Stack;
//
//class Solution {
//    public class TreeNode {
//     int val;
//      TreeNode left;
//     TreeNode right;
//      TreeNode(int x) { val = x; }
//  }
//    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//        Stack<TreeNode> stack1=new Stack<>();
//        Stack<TreeNode> stack2=new Stack<>();
//        getPath(root,p,stack1);
//        getPath(root,q,stack2);
//        int size1=stack1.size();
//        int size2=stack2.size();
//
//        if(size1>size2){
//            int count=size1-size2;
//            while(count!=0){
//                stack1.pop();
//            }
//        }else{
//             int count=size2-size1;
//            while(count!=0){
//                stack2.pop();
//            }
//
//        }
//        while(!stack1.isEmpty()){
//            if(stack1.peek().equals(stack2.peek())){
//                return stack1.peek();
//            }
//            stack1.pop();
//            stack2.pop();
//        }
//        return null;
//
//    }
//     public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
//        if(root==null){
//            return false;
//        }
//        stack.push(root);
//        if(root==node){
//            return true;
//        }
//        boolean left=getPath(root.left,node,stack);
//        if(left){
//            return true;
//        }
//        boolean right=getPath(root.right,node,stack);
//        if(right){
//            return true;
//        }
//        stack.pop();
//        return false;
//
//    }
//    public TreeNode buildTree(int[] preorder, int[] inorder) {
//        return buildTreeChild(preorder,inorder,0,0,inorder.length);
//
//
//    }
//    public TreeNode buildTreeChild(int[] preorder, int[] inorder,int i,int begin,int end){
//        if(begin>end){
//            return null;
//        }
//        int index=preorder[i];
//        i++;
//        TreeNode root=new TreeNode(index);
//        int rootIndex=find(inorder,index,begin,end);
//        root.left=buildTreeChild(preorder,inorder,i,begin,rootIndex-1);
//        root.right=buildTreeChild(preorder,inorder,i,rootIndex+1,end);
//        return root;
//    }
//    public int find( int[] inorder,int value,int begin,int end){
//        for (int i = begin; i <=end ; i++) {
//            if(inorder[i]==value){
//                return i;
//            }
//
//        }
//        return -1;
//    }
//
//
//
//        public  int preIndex ;
//        public TreeNode buildTree(int[] preorder, int[] inorder) {
//            return buildTreeChild(preorder,inorder,0,inorder.length-1);
//        }
//
//        private TreeNode buildTreeChild(int[] preorder, int[] inorder,int inBegin,int inEnd) {
//            if(inBegin > inEnd) {
//                return null;
//            }
//            //1、创建根节点
//            TreeNode root =  new TreeNode(preorder[preIndex]);
//            //2. 在中序遍历的字符串当中 找到当前根节点的下标
//            int rootIndex = findRootIndex(inorder,inBegin,inEnd,preorder[preIndex]);
//            preIndex++;//F
//            //3. 分别创建左子树和右子树
//            root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
//            root.right = buildTreeChild(preorder,inorder,rootIndex+1,inEnd);
//            return root;
//        }
//
//        private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
//            for(int i = inBegin; i <= inEnd;i++) {
//                if(inorder[i] == key) {
//                    return i;
//                }
//            }
//            return -1;
//        }
//
//
//}